package main

import (
	"data_structure_and_algorithms/sorting"
	"fmt"
)

//https://www.cnblogs.com/onepixel/articles/7674659.html

/*

 */

func Sort(src []int) (res [] int) {

	res = make([]int, len(src))

	copy(res, src)

	quickSort(res, 0, len(res)-1)

	fmt.Println(res)

	return nil
}

func quickSort(arr [] int, start, end int) {

	if start < end {
		i, j := start, end
		key := arr[(start+end)/2]
		for i < j {
			for arr[i] < key {
				i++
			}
			for arr[j] > key {
				j--
			}
			if i <= j {
				arr[i], arr[j] = arr[j], arr[i]
				i++
				j--
			}
		}

		if start < j {
			quickSort(arr, start, j)
		}
		if end > i {
			quickSort(arr, i, end)
		}
	}
}

func main() {

	arr := sorting.Init(100000, 100)

	fmt.Println(arr)
	//[]int{17, 3, 47, 65, 4, 95, 83, 27, 99, 12}
	Sort(*arr)

	//fmt.Println(*arr)
}
